/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 打乱字符串顺序，使得相邻的字母不相同
 * 
 * 
 * 思路：隔一个填一个，先填词频高的,从前面开始填起，如果到了最后，又从第二个填起
 * 
 * @author zhong
 *
 */
public class ReorganizeString {
	class Frequency implements Comparable<Frequency> {
		char ch;
		int freq;

		public Frequency(char ch) {
			this.ch = ch;
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return ch + ":" + freq;
		}

		@Override
		public int compareTo(Frequency o) {
			if (this.equals(null)) {
				return -1;
			}
			if (o.equals(null)) {
				return 1;
			}
			return this.freq - o.freq;
		}

	}

	public String rearrangeString(String s, int k) {
		HashMap<Character, Integer> map = new HashMap<>();
		for (char c : s.toCharArray()) {// 统计词频
			Integer cnt = map.get(c);
			if (cnt == null)
				cnt = 0;
			map.put(c, cnt + 1);
		}
		Queue<Map.Entry<Character, Integer>> mapQueue = new PriorityQueue<>(
				new Comparator<Map.Entry<Character, Integer>>() {
					@Override
					public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
						return o2.getValue() - o1.getValue();
					}
				});// 按照词频由大到小排序
		mapQueue.addAll(map.entrySet());// 原始优先队列，里面是<k,v>
		Queue<Map.Entry<Character, Integer>> queue = new LinkedList<>();// 新优先队列，放“禁止”放的字符序列
		StringBuilder sb = new StringBuilder();
		while (!mapQueue.isEmpty()) {
			Map.Entry<Character, Integer> current = mapQueue.poll();
			sb.append(current.getKey());
			current.setValue(current.getValue() - 1);
			queue.offer(current);
			if (queue.size() < k)// k是指定的间隔距离，如果已经加入过<k种字符，则继续，否则看是否需要放回前k个放到字符串的
				continue;
			Map.Entry<Character, Integer> temp = queue.poll();// 如果词频=0则不放回
			if (temp.getValue() > 0)// 刚好第前k个“解禁”，如果词频=0则不放回
				mapQueue.offer(temp);
		}
		return sb.toString().length() == s.length() ? sb.toString() : "";
	}

	public String reorganizeString(String S) {
		int n = S.length();
		System.out.println(n);
		Map<Character, Frequency> ch2frequencies = new HashMap<>();
		// 统计词频并排序
		for (int i = 0; i < n; i++) {
			if (!ch2frequencies.containsKey(S.charAt(i))) {
				ch2frequencies.put(S.charAt(i), new Frequency(S.charAt(i)));
			}
			ch2frequencies.get(S.charAt(i)).freq++;
		}
		ArrayList<Frequency> frequencies = new ArrayList<>(ch2frequencies.values());
		Collections.sort(frequencies);
		System.out.println(frequencies);
		// 先填充最大的
		StringBuilder sBuilder = new StringBuilder(n);
		// 填充为-
		for (int i = 0; i < n; i++) {
			sBuilder.append('-');
		}
		int start = 0;
		for (int j = frequencies.size() - 1; j >= 0; j--) {
			int count = 0;
			for (; count < frequencies.get(j).freq; count++) {
				if (start >= n) {
					if (sBuilder.charAt(1) != '-')
						return "";
					start = 1;
				}
				sBuilder.setCharAt(start, frequencies.get(j).ch);
				if (sBuilder.charAt(0) == sBuilder.charAt(1)) {
					return "";
				}
				start += 2;
			}
			System.out.println(j);
			System.out.println(sBuilder);
		}
		return sBuilder.toString();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String string = "tndsewnllhrtwsvxenkscbivijfqnysamckzoyfnapuotmdexzkkrpmppttficzerdndssuveompqkemtbwbodrhwsfpbmkafpwyedpcowruntvymxtyyejqtajkcjakghtdwmuygecjncxzcxezgecrxonnszmqmecgvqqkdagvaaucewelchsmebikscciegzoiamovdojrmmwgbxeygibxxltemfgpogjkhobmhwquizuwvhfaiavsxhiknysdghcawcrphaykyashchyomklvghkyabxatmrkmrfsppfhgrwywtlxebgzmevefcqquvhvgounldxkdzndwybxhtycmlybhaaqvodntsvfhwcuhvuccwcsxelafyzushjhfyklvghpfvknprfouevsxmcuhiiiewcluehpmzrjzffnrptwbuhnyahrbzqvirvmffbxvrmynfcnupnukayjghpusewdwrbkhvjnveuiionefmnfxao";// "vvvlo"//aaab//aab
		// "eweweweweweweweweweweweweweueueueueueueueueueueueueueueuhuhuhuhuhuhshshs
		// hshshshshshshshshshshshshshshshshphphphpcpcpcpcpcpcpcpcpcpcpcpcpcpcpcrcrcrc
		// rcrcrcrcrcrcrcrcrmrmrmrmrmrmrmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmxmgmgvgvgvgv
		// gvgvgvgvgvgvgvgvgvgvgvgvovovovovovovovovonononononononononbnbnbnbnbnbnbnbnbn
		// bnbnbnbnbnbabaiaiaiaiaiaiaiaiaiaiaiaiaiaiaiaiatatatatatftftftftftftftftftftftf
		// dfdfdfdfdfdfdfdfdfdfdydydydydyzyzyzyzyzyzyzyzyzyzyzyzyzyzyjyjyjyjkjkjkjkjkjkjk
		// jklklklklklklklklklklklkqkqkqwqwqwqwqwqwqwqwq"
		// ehcmvnafykw
		// wusprxgobitdzjlq
		System.out.println(new ReorganizeString().reorganizeString(string));
	}

}
